package com.ryujung.hash;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;

public class MyHashSetWithoutGeneric {

    private Node[] arr;
    transient int size = 0;
    double factor = 0.75d;
    public static final int DEFAULT_SIZE = 1 << 5;

    public MyHashSetWithoutGeneric() {
    }

    public void add(int val) {
        if (contains(val))
            return;
        if (this.arr == null) {
            this.arr = new Node[DEFAULT_SIZE];
        } else if (this.size + 1 >= arr.length * factor) {
            resize();
        }

        int hash = hash(val);
        Node newNode = new Node(hash, val, null);
        int binNum = hash & (arr.length - 1);
        if (arr[binNum] != null) {
            Node node = arr[binNum];
            while (node.next != null) {
                node = node.next;
            }
            node.next = newNode;
        } else {
            this.size++;
            arr[binNum] = newNode;
        }

    }

    private int hash(int val) {
        return val * 3 + 2;
    }

    public void resize() {
        int newCap = arr.length << 1;
        Node[] oldArr = this.arr;
        Node[] newTable = new Node[newCap];
        int newSize = 0;
        for (int i = 0; i < oldArr.length; i++) {
            Node node = arr[i];
            while (node != null) {
                if (newTable[node.hash & (newCap - 1)] == null) {
                    newTable[node.hash & (newCap - 1)] = node;
                    newSize++;
                } else {
                    Node tail = newTable[node.hash & (newCap - 1)];
                    while (tail.next != null) {
                        tail = tail.next;
                    }
                    tail.next = node;
                }
                node = node.next;
            }
        }
        this.size = newSize;
        this.arr = (Node[]) newTable;
    }

    public void remove(int value) {
        if (!contains(value)) {
            return;
        }

        int hash = hash(value);
        int binNum = hash & (arr.length - 1);
        if (arr[binNum] != null) {
            Node curNode = arr[binNum];
            if (curNode.value == value) {
                arr[binNum] = curNode.next;
                if (arr[binNum] == null) {
                    this.size--;
                }
                return;
            }
            Node preNode = curNode;
            while (curNode != null) {
                if (curNode.value != value) {
                    preNode = curNode;
                    curNode = curNode.next;
                } else {
                    preNode.next = curNode.next;
                    curNode.next = null;
                    break;
                }
            }

        }

    }

    public boolean contains(int value) {
        int hash = hash(value);
        int binNum = size == 0 ? 0 : hash & (arr.length - 1);
        if (arr == null)
            return false;
        if (arr[binNum] != null) {
            Node curNode = arr[binNum];
            while (curNode != null && curNode.value != value) {
                curNode = curNode.next;
            }
            if (curNode != null) {
                return true;
            }
        }
        return false;
    }

    static class Node {
        int hash;
        private int value;
        private Node next;

        Node(int hash, int val, Node next) {
            this.hash = hash;
            this.value = val;
            this.next = next;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("MyHashSet[");

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != null) {
                Node temp = arr[i];
                while (temp != null) {
                    sb.append(temp.value).append(",");
                    temp = temp.next;
                }
            }
        }
        if (sb.indexOf(",") != -1) {
            sb.deleteCharAt(sb.lastIndexOf(","));
        }
        sb.append("]");
        return sb.toString();
    }

    public int size() {
        return this.size;
    }

    public static void main(String[] args) throws Exception {
        String[] act = new String[] { "contains", "remove", "add", "add", "contains", "remove", "contains",
                "contains", "add", "add", "add", "add", "remove", "add", "add", "add", "add", "add", "add", "add",
                "add", "add", "add", "contains", "add", "contains", "add", "add", "contains", "add", "add", "remove",
                "add", "add", "add", "add", "add", "contains", "add", "add", "add", "remove", "contains", "add",
                "contains", "add", "add", "add", "add", "add", "contains", "remove", "remove", "add", "remove",
                "contains", "add", "remove", "add", "add", "add", "add", "contains", "contains", "add", "remove",
                "remove", "remove", "remove", "add", "add", "contains", "add", "add", "remove", "add", "add", "add",
                "add", "add", "add", "add", "add", "remove", "add", "remove", "remove", "add", "remove", "add",
                "remove", "add", "add", "add", "remove", "remove", "remove", "add", "contains", "add" };
        Object[][] params = new Object[][] { { 72 }, { 91 }, { 48 }, { 41 }, { 96 }, { 87 }, { 48 }, { 49 }, { 84 },
                { 82 }, { 24 }, { 7 }, { 56 }, { 87 }, { 81 }, { 55 }, { 19 }, { 40 }, { 68 }, { 23 }, { 80 }, { 53 },
                { 76 }, { 93 }, { 95 }, { 95 }, { 67 }, { 31 }, { 80 }, { 62 }, { 73 }, { 97 }, { 33 }, { 28 }, { 62 },
                { 81 }, { 57 }, { 40 }, { 11 }, { 89 }, { 28 }, { 97 }, { 86 }, { 20 }, { 5 }, { 77 }, { 52 }, { 57 },
                { 88 }, { 20 }, { 48 }, { 42 }, { 86 }, { 49 }, { 62 }, { 53 }, { 43 }, { 98 }, { 32 }, { 15 }, { 42 },
                { 50 }, { 19 }, { 32 }, { 67 }, { 84 }, { 60 }, { 8 }, { 85 }, { 43 }, { 59 }, { 65 }, { 40 }, { 81 },
                { 55 }, { 56 }, { 54 }, { 59 }, { 78 }, { 53 }, { 0 }, { 24 }, { 7 }, { 53 }, { 33 }, { 69 }, { 86 },
                { 7 }, { 1 }, { 16 }, { 58 }, { 61 }, { 34 }, { 53 }, { 84 }, { 21 }, { 58 }, { 25 }, { 45 }, { 3 } };

        String packageName = MyHashSetWithoutGeneric.class.getPackage().getName();
        Class<?> cls = Class.forName(packageName + ".MyHashSetWithoutGeneric");
        Object instance = cls.getDeclaredConstructor().newInstance();
        long begin = System.currentTimeMillis();
        Object[] result = test(instance, act, params);
        long end = System.currentTimeMillis();
        System.out.println("test cost: " + (end - begin) + "ms.");
        HashSet<Integer> set = new HashSet<>();
        Object[] trueResult = test(set, act, params);
        for (int i = 0; i < trueResult.length; i++) {
            if (!Objects.equals(result[i], trueResult[i])) {
                System.out.println(
                        "answer error! act:" + act[i] + ",your result:" + result[i] + ",expect: " +
                                trueResult[i]);
                break;
            }
        }
        System.out.println("test pass.");
        System.out.println(Arrays.toString(result));
        System.out.println(Arrays.toString(trueResult));
    }

    public static Object[] test(Object instance, String[] act, Object[][] params) throws Exception {
        Object[] result = new Object[act.length];
        Class<? extends Object> cls = instance.getClass();
        Method[] methods = cls.getMethods();
        for (int i = 1; i < act.length; i++) {
            for (Method method : methods) {
                if (method.getName().equals(act[i])) {
                    result[i] = act[i].equals("contains") ? method.invoke(instance, params[i]) : null;
                }
            }
        }
        return result;
    }

}
